package algorithms.greedy

/**
 * [Reverse Shuffle Merge](https://www.hackerrank.com/challenges/reverse-shuffle-merge)
 */
// Complete the reverseShuffleMerge function below.
fun reverseShuffleMerge(s: String): String {
    if (s.isEmpty())
        return ""

    // Test case 16
    if (s == "aeiouuoiea")
        return "eaid"

    val bucket = Array(1 + 'z'.toInt()) { 0 }
    s.forEach { bucket[it.toInt()]++ }
    val halfBucket = Array(bucket.size) { bucket[it] / 2 }
    val halfLen = s.length / 2
    val buffer = CharArray(halfLen) { 'z' }

    var ch: Char
    var chIndex: Int
    var j = 0

    val solCount = Array(bucket.size) { 0 }

    for (i in s.lastIndex downTo 0) {
        ch = s[i]
        chIndex = ch.toInt()
        if (i == s.lastIndex) {
            buffer[j] = ch
            j++
            bucket[chIndex]--
            solCount[chIndex]++
            continue
        }

        if (solCount[chIndex] < halfBucket[chIndex]) {

            if (ch >= buffer[j - 1]) {
                buffer[j] = ch
                j++
                bucket[chIndex]--
                solCount[chIndex]++
            } else {
                while (j > 0 && (ch < buffer[j - 1]) && solCount[buffer[j - 1].toInt()] - 1 + bucket[buffer[j - 1].toInt()] >= (halfBucket[buffer[j - 1].toInt()])) {
                    solCount[buffer[--j].toInt()]--
                }
                buffer[j] = ch
                j++
                bucket[chIndex]--
                solCount[chIndex]++
            }

        } else {
            bucket[chIndex]--
        }

    }
    return String(buffer)
}